// Exploit multiset to do insertion sort on top of an efficient data structure.
// O(nlogn)

#include <iostream>
#include <set>



int 
main(int argc, char* argv[])
{
  int n;

  if (argc == 1)
    {
      n = 10;
    }
  else
    {
      n = atoi(argv[1]);
    }

  srand ( time(NULL) );
  
  std::cerr << "Original array:" << std::endl;
  int s[n];
  int i;

  for (i = 0; i < n; ++i)
    {
      s[i] = rand() % 100;
      std::cerr << s[i] << " ";
    }
  std::cerr << std::endl;

  std::multiset<int> storage;
  for (i = 0; i < n; ++i)
    {
      storage.insert(s[i]);
    }

  std::cerr << "Sorted array:" << std::endl;
  i = 0;
  for (std::set<int>::const_iterator it = storage.begin(); it != storage.end(); ++it, ++i)
    {
      s[i] = *it;
      std::cerr << s[i] << " ";
    }
  std::cerr << std::endl;
}
